A program specifies a computation.
A real-time program specifies a computation of one or more tasks that have real-time constraints.
A task is a portion of a computation of a program.
A real-time constraint specifies that the computation of a task must have progressed up to a certain point, which could for example be the end of the task, within a predefined duration in wall clock time. The predefined duration in time is also known as the time between the activation of a task and a deadline of a task.
When the real-time program is executed, a plurality of tasks specified by the program may execute concurrently.
One or more real-time tasks may execute concurrently with tasks that do not have real-time constraints. The latter tasks are also referred to as non-real-time tasks (non-RT tasks).
A real-time task (RT-task) typically executes on the same execution unit from the start of said task to the end of said task.
When a plurality of tasks execute on the same execution unit, concurrent execution means that the plurality of tasks use the execution unit in a time sharing manner. Time sharing refers to the allocation of each task of the concurrent tasks to the execution unit. Time sharing is controlled by a scheduler. The scheduler may be a hardware or software scheduler or a combination thereof. Preferably the scheduler is controlled by the operating system. The operating system is preferably a real-time operating system.
When referring to “time” in the context of real-time computations, two different concepts are distinguished: The first concept of “time” concerns “execution time,” sometimes also referred to as “CPU time,” which refers to the time that a task actually makes use of an execution unit. The second concept of “time” concerns “wall clock time.” Likewise, the term “duration” refers to wall clock time, which is the difference between an end point and a start point in wall clock time. For example, the start of a task and the deadline of a task are typically specified as absolute or relative points in wall clock time, i.e., in wall clock times. The wall clock time between the activation time of a task and its end is also referred to as “response time”. When the execution unit is not shared among a plurality of tasks, only a single task is allocated to the execution unit, the concepts of “wall clock time” and “execution time” are identical under the assumption that the single task is always active. A task is active if it is ready to execute, i.e., if it is not waiting, e.g., for input which may, e.g., be provided by other tasks. When it is clear from the context, the wording in the following uses the term “time”, otherwise it is explicitly distinguished between “execution time” and “wall clock time”.
Similar to sharing of the execution unit, other resources may be shared among concurrent tasks wherein sharing is likewise controlled by a resource allocator which may be a unit of an operating system. The present disclosure and the techniques presented herein primarily relate to the sharing of the execution units wherein the resource allocator is a scheduler. When sharing concerns resources other than an execution unit, this is explicitly mentioned herein. The following terms are typically used in the real-time theory: “active resource” refers, e.g., to an execution unit or communication bus; “passive resource” refers, e.g., to variables or memory shared among different OS threads.
An execution unit is typically a processor core. Modem processors typically include a plurality of cores and are thus called multi-core or many-core processors. The architecture of such processors is commonly such that the cores share common resources on the processor, for example a cache, a communication bus, and a memory interface. This type of sharing due to the architecture of a multicore-processor has the effect that the execution of a first task on a first core may affect the timing of an execution of a second task on a second execution core.
For real-time programs, this type of resource sharing based on the processor architecture affects the prediction of the worst-case execution time. Specifically, the worst case execution time, WCET, which is an execution time in the above sense and which is predicted by conventional methods that take into account any possible and specifically also extremely unlikely interactions among processor cores through their sharing of architectural resources, may lead to extremely pessimistic WCET predictions that are much above realistic common case execution times. This large discrepancy makes the prediction results of WCET determined by conventional methods of little use on multicore architecture, since, when provided as input to a scheduler, lead to very pessimistic real-time schedules that do not achieve efficient resource utilization. While the problem is particularly relevant for multicore architectures as described, resource sharing also occurs when multiple concurrent tasks execute in a time-sharing manner on a processor with a single execution unit, which is e.g. a processor core, since, for example, the cache memory associated with the execution unit is shared among the concurrent tasks.
Claire Pagetti, Christine Rochange: “Runtime monitoring of time-critical tasks in multicore systems” (available at materials.dagstuhl.de/files/15/15121/15121.ClairePagetti.ExtendedAbstract. pdf) describes a method which monitors critical tasks at run time, wherein in case of a delay and thus a possible violation of real-time properties, other less critical tasks are interrupted to allow the critical task to continue its execution in a timely and efficient manner, without sharing resources of the execution unit with other tasks.
Michael Paulitsch: “Challenges for the Use of Multicore Processors in Mixed-Criticality Systems with Focus on Temporal Aspects”, RTAS 2014 (available at: 2014.rtas.org/wp-content/uploads/Paulitsch.pdf). Slide number 11: “WCET for Multi-Core Computers Combined with Monitoring” describes the possibility to execute tasks with real-time constraints on multicore processors.
To summarize the aforementioned problem, the high discrepancy between predicted WCET and common case execution times on modern processor architectures makes conventional techniques of WCET inefficient to control real-time execution and scheduling decisions on such architectures. The present disclosure addresses this problem.